P6825 「EZEC-4」求和

i=1nj=1ngcd(i,j)i+j\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}

d=1ni=1nj=1n[gcd(i,j)=d]di+j\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}

d=1ni=1ndj=1nd[gcd(i,j)=1]d(i+j)d\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor } [\gcd(i,j)=1]d^{(i+j)d}

d=1nt=1ndμ(t)i=1ndtj=1ndtd(i+j)dt\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{dt} \rfloor } d^{(i+j)dt}

d=1nt=1ndμ(t)(i=1ndtdidt)2\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) (\sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor } d^{idt})^2

d=1nddt=1ndμ(t)dt(i=1ndtdi)2\sum_{d=1}^n d^d \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) d^t (\sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor } d^i)^2

d=1nddt=1ndμ(t)dt(1dndt1d)2\sum_{d=1}^n d^d \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) d^t (\frac{1-d^{\lfloor \frac{n}{dt} \rfloor}}{1-d})^2


T=1ndTdTμ(Td)(i=1nTdi)2\sum_{T=1}^n \sum_{d|T} d^T \mu(\frac{T}{d}) (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor }d^{i})^2

T=1n(dTdTμ(Td)(1dTd1d)2)\sum_{T=1}^n \left( \sum_{d|T} d^T \mu(\frac{T}{d})(\frac{1-d^{\lfloor \frac{T}{d} \rfloor}}{1-d})^2 \right)